package str;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCodeForStr {

    /**
     * 划分字母区间:
     * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
     * 输入：S = "ababcbacadefegdehijhklij"
     * 输出：[9,7,8]
     */
    public List<Integer> p763(String str) {
        if (str == null) {
            return new ArrayList<>(0);
        }
        // 1. 记录每个字符出现的次数
        int[] count = new int[26];
        for (char c : str.toCharArray()) {
            count[c - 'a'] += 1;
        }
        // 2. 划分区间
        List<Integer> range = new ArrayList<>();
        Map<Character, Integer> subMap = new HashMap<>();
        label:
        for (char c : str.toCharArray()) {
            if (!subMap.containsKey(c)) {
                subMap.put(c, 0);
            }
            subMap.put(c, subMap.get(c) + 1);
            // 检测是否满足要求
            int len = 0;
            for (Map.Entry<Character, Integer> item : subMap.entrySet()) {
                if (item.getValue().intValue() != count[item.getKey() - 'a']) {
                    continue label;
                }
                len += item.getValue();
            }
            // 如果满足要求
            range.add(len);
            subMap.clear();
        }
        return range;
    }

    @Test
    public void testp763() {
        LeetCodeForStr leetCodeForStr = new LeetCodeForStr();
        List<Integer> range = leetCodeForStr.p763("ababcbacadefegdehijhklij");
        System.out.println(range);
    }
}
